As described in U.S. patent application Ser. No. 09/923,709 by Rachel Learned, filed Aug. 7, 2001 and incorporated herein by reference, a system is described in which multiple users are able to communicate on the same frequency at the same time through the utilization of parameter estimation techniques which are utilized by a multi-user detector. The output of the multi-user detector is the best guess as to what the individual bits were for the individual user.
Moreover, in an article by Paul D. Alexander, Mark C. Reed, John A. Asenstorfer and Christian B. Schlagel in IEEE Transactions on Communications, vol. 47, number 7, July 1999, entitled “Iterative Multi-User Interference Reduction: Turbo CDMA,” a system is described in which multiple users can transmit coded information on the same frequency at the same time, with the multi-user detection system separating the scrambled result into interference-free voice or data streams.
Multi-user detection units, in general, operate by examining the entire number of possibilities for each bit, which is a computationally complex operation. Thus for those multi-user detectors that examine the entire space, real-time operation is often elusive.
For multi-user detectors of the type of iterative multi-user detection system described in the above article, currently called a Turbo MUD, algorithms examine the space of all possible combinations. A MUD algorithm within the Turbo MUD system determines discrete estimates of the transmitted channel symbols, with the estimates then provided to a bank of single-user decoders (one decoder for each user) to recover the input bit streams of all transmitted signals.
Two general types of multi-user detectors within the Turbo MUD system are possible: those that provide hard outputs, which are discrete values, and those that provide soft outputs, which indicate both the discrete estimate and the probability that the estimate is correct.
However, single-user decoders operating on hard values, or discrete integers, have unacceptable error rates when there is a large amount of interference. The reason is that discrete integers do not provide adequate confidence values on which the single-user decoder can operate. These decoders operate better on so-called soft inputs in which confidence values can range from −1 to 1, such as for instance 0.75 as opposed to being either −1 or +1.
In an attempt to provide so-called soft values which can then be utilized by a single-user decoder, these soft values can be generated by the multi-user detector. However the processing takes an inordinate amount of time. As a result, these systems do not produce real-time results. Since single-user decoders operate best on soft values, it is often times the case that the computational complexity for the MUD to enable it to generate these soft values makes it impossible to get a real-time result.
In an attempt to provide real-time performance by reducing the computational complexity of an iterative multi-user detector which can produce soft values, the above-mentioned paper suggests algorithms for examining less than the total number of possibilities for each of the bits of data that are coming in from the multiple users. The “shortcuts” taken by this reduced complexity approach cause errors; and combating these errors by increasing the parameters used withing the MUD algorithm and by increasing the number of iterations of the system completely nullifies any advantage.
Thus, while soft values can be generated in the above manner, the entire detection system is slowed down in generating these soft values.
It will be appreciated that these soft values, rather than being integers which would be considered to be hard values, are real numbers, which in effect, permit a single user decoder to better error correct the output of the multi-user detector and thereby provide a more robust bit stream that will faithfully track the original input for a given user.
In one embodiment, the single user detector is a so-called BCJR Decoder, which stands for a Bahl, Cocke, Jelinek, and Raviv Decoder. A characteristic of such a decoder is that it utilizes maximum a posteriori or MAP algorithms to error-correct the incoming signals. It will be appreciated that MAP error correction depends upon soft values in order to be able to increase the probability that the decoded bits will faithfully reflect the input.
The result of utilizing BCJR decoders along with Turbo MUDs is that as many as 100 users can transmit on a single frequency at the same time, with the intelligence carried by each of the users separated and decoded in such a manner that the probability that the decoded bit stream is correct is quite high.
As stated above, the problem with Turbo MUDs is that while the individual communications channels can be separated and thereby rendered usable, real-time processing has been elusive due to the MAP and maximum likelihood correction algorithms normally utilized in a Turbo MUD.
Moreover, when dealing with hand-held communications units such as wireless handsets, the amount of processing within the device is limited, as is the amount of computational complexity that is allowed. In order to provide real-time performance both at a cell site and the handset, it therefore becomes important to be able to reduce the amount of computational complexity and processing time so as to achieve real-time performance.